package pro.softzhang.algo.lc100;

import pro.softzhang.algo.flag.theme.TReverse;
import pro.softzhang.algo.flag.x.XOptimal;

import java.util.*;

@TReverse
public class LC151_ReverseWordsInAString {
    public static void main(String[] args) {
        String str = "the sky is blue";
        System.out.println(new Solution1().reverseWords(str));
    }

    @XOptimal
    static
    class Solution {
        public String reverseWords(String s) {
            s = s.trim();
            List<String> words = Arrays.asList(s.split("\\s+"));
            Collections.reverse(words);
            return String.join(" ", words);
        }
    }

    static
    class Solution1 {
        public String reverseWords(String s) {
            int left = 0, right = s.length() - 1;
            while(left <= right && s.charAt(left) == ' ') {
                left++;
            }
            while(right >= left && s.charAt(right) == ' ') {
                right--;
            }

            StringBuilder word = new StringBuilder();
            Deque<String> reversed = new LinkedList<>();
            while(left <= right) {
                char c = s.charAt(left);
                if(c != ' ') {
                    word.append(c);
                } else if(word.length() != 0 && c == ' ') {
                    reversed.offerFirst(word.toString());
                    word.setLength(0);
                }
                left++;
            }
            reversed.offerFirst(word.toString());
            return String.join(" ", reversed);
        }
    }
}
